On the Definiteness of Earth Mover's Distance Yields and Its Relation to Set Intersection

摘要

Positive definite kernels are an important tool in machine learning thatenable efficient solutions to otherwise difficult or intractable problems byimplicitly linearizing the problem geometry. In this paper we develop aset-theoretic interpretation of the Earth Mover's Distance (EMD) and proposeEarth Mover's Intersection (EMI), a positive definite analog to EMD for sets ofdifferent sizes. We provide conditions under which EMD or certainapproximations to EMD are negative definite. We also present apositive-definite-preserving transformation that can be applied to any kerneland can also be used to derive positive definite EMD-based kernels and showthat the Jaccard index is simply the result of this transformation. Finally, weevaluate kernels based on EMI and the proposed transformation versus EMD invarious computer vision tasks and show that EMD is generally inferior even withindefinite kernel techniques.